CSE 311: Homework 2 Part 2

Due: Monday, April 20th by 6:00 PM

Instructions

Write up carefully argued solutions to the following problems. Each solution should be clear enough that it can explain (to someone who does not already understand the answer) why it works. However, you may use results from lecture, the reference sheets, and previous homework without proof.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, the write up must clearly be your own, and moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution via Gradescope. In particular:

• Each numbered task should be solved on its own page (or pages). Do not write your name on the individual pages. (Gradescope will handle that.)

• When you upload your pages, make sure each one is properly rotated. If not, you can use the Gradescope controls to turn them to the proper orientation.

• Follow the Gradescope prompt to link tasks to pages.

• You are not required to typeset your solution, but your submission must be legible. It is your responsibility to make sure solutions are readable — we will not grade unreadable write-ups.

Task 1 – Make the First Prove

For each of the following, write a formal proof that the claim holds.

1. Given $(p \wedge q) \to r$ and $\neg r \vee s$, prove $\neg s \to (\neg p \vee \neg q)$.

   You are free to use equivalences and Direct Proof in addition to Modus Ponens, Intro $\wedge$, Elim $\wedge$, Intro $\vee$, and Elim $\vee$.

2. Given $\forall x,\, (P(x) \wedge Q(x)) \to R(x)$ and $\forall x,\, P(x)$, prove $\forall x,\, Q(x) \to R(x)$.

   You are free to use Direct Proof, Intro $\forall$, Elim $\forall$, Intro $\exists$, and Elim $\exists$ in addition to the propositional rules. Equivalences are not allowed.

Task 2 – Pack Up the Proving Van

For each of the following, write a formal proof that the claim holds.

In addition to the propositional rules from Task 1, your proofs are also allowed to use Cases and the Latin rules. Equivalences are not allowed.

1. Given $p\lor\neg q$, $p\to r$, $q \lor s$, and $(r\lor s)\to(v\land u)$, prove $\neg r\lor (v\land u)$.

   Hint: Use Cases on the disjunction $p\lor\neg q$ to conclude $r\lor s$.

2. Given $s \to (p \vee \neg q)$, $(q \wedge p) \vee (s \wedge \neg p)$, and $q \vee p$, it follows that $q$ holds.

   Hint: First prove $\neg(s \wedge \neg p)$ by contradiction, using the Contradiction and Absurdum rules. Then use $\neg(s \wedge \neg p)$ together with the second given to conclude $q$.

Task 3 – Div and Let Div

Let the domain of discourse be the integers. Consider the following claim: $$\forall a\, \forall b\, \forall c \left( (a \mid b) \wedge (a \mid c) \to (a \mid (b + c)) \right)$$ In English, this claim says that sums of divisible integers are divisible: if $a$ divides both $b$ and $c$, then $a$ also divides their sum $b + c$. As an example, if you know that $7$ divides both $49$ and $21$, you know that $7$ also divides $49 + 21 = 70$.

1. Write a formal proof that the claim holds.

2. Translate your formal proof to an English proof.

   Keep in mind that your proof will be read by a human, not a computer, so you should explain the algebra steps in more detail, whereas some of the predicate logic steps (e.g., Elim $\exists$) can be skipped.

Task 4 – Optional Practice Problems (Extra Credit)

The following problems are optional and do not need to be submitted. However, you may submit solutions and receive a small amount of extra credit for any 5 (of the 16) subparts, graded solely on completion. For the maximum extra credit score, at least one subpart from each of the three sections should be submitted.

1. Proofs with propositions (write a formal proof)

   1. Given $p\lor q$, $r\land\neg p$, and $\neg(q\land\neg s)$, it follows that $s\land r$.

   2. Given $(q\land r)\to(s\lor u)$, $\neg p\to(r\land \neg u)$, and $p\lor q$, it follows that $\neg p\to s$.

   3. Given $(p\to r)\land(q\lor p)$, $\neg q\land\neg r$, and $r\to(s\lor v)$, it follows that $r\to(s\land v)$.

   4. Given $a\to(b\lor c)$, $c\to(\neg d\land a)$, $e\land c$, it follows that $\neg d\land(b\lor c)$.

   5. Given $p\land (q\land s)$ and $q\to r$, it follows that $(r\lor t) \land (r\lor s)$.

   6. Given $\neg(b\lor d)\to\neg a$, $f\to(b\lor d)$, and $(c\land f)\land \neg b$, it follows that $d$.

   7. Given $(q\to\neg s)\leftrightarrow(\neg r\to u)$ and $u\land s$, it follows that $\neg q$.

   8. Given $(q\lor\neg p)\to r$, $(q\lor p)\to u$, and $p$, it follows that $(p\to q)\to(r\land u)$.

   9. Given $(q\lor\neg p)\to r$, $(q\lor p)\to u$, and $p$, it follows that $p\to q\to(r\land u)$. (Note the differing parentheses from above)

2. Proofs with quantifiers (write a formal proof)

   1. Given $\exists x\,P(x)$, $\forall x\, R(x,c)$, and $\forall x\,(P(x)\to R(c,x)$, it follows that $\exists x\,\exists y\, (R(x,y)\land R(y,x))$.

   2. Given $\forall x\, (R(x,c)\land Q(x))$ and $\forall x\, \forall y\, (R(x,y)\to R(y,x))$, it follows that $\forall x\, \exists y\, (R(x,y)\land R(y,x))$.

   3. Given $\forall x\, (P(x)\to Q(x))$, it follows that $(\forall x\, P(x))\to(\forall x\,Q(x))$.

   4. Given $\forall x\,(P(x)\to R(x,c))$ and $\forall x\,\forall y\, ((Q(x)\land R(x,y))\to R(y,x))$, it follows that $(\forall x\, (P(x)\land Q(x)))\to(\forall x\, R(c,x))$.

3. Proofs involving definitions (it may be easier to do these in English, but you can try formal too)

   1. Prove that the product of two odd integers is odd.

   2. Prove that the sum of two rational numbers is rational.

   3. Prove that for every positive integer $a$, $\operatorname{gcd}(a,a)=a$.